package features.advance.leetcode.array.medium;

import java.util.HashMap;
import java.util.Map;

/**
 *  剑指 Offer II 011. 0 和 1 个数相同的子数组
 *
 *  难度：中等
 *
 * 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [0,1]
 * 输出: 2
 * 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
 * 示例 2:
 *
 * 输入: nums = [0,1,0]
 * 输出: 2
 * 说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * nums[i] 不是 0 就是 1
 *
 *
 * 注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/
 *
 *
 * @author LIN
 * @date 2021-08-30
 */
public class Offer2_11 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int findMaxLength(int[] nums) {
                Map<Integer, Integer> map = new HashMap<>();
                map.put(0, -1);
                int pre_sum = 0;
                int ret = 0;
                for (int i = 0; i < nums.length; i++) {
                    pre_sum += nums[i] == 0 ? -1 : 1;
                    if (map.containsKey(pre_sum)) {
                        ret = Math.max(ret, i - map.get(pre_sum));
                    } else {
                        map.put(pre_sum, i);
                    }
                }
                return ret;
            }
        };
        solution = new Solution(){
            @Override
            public int findMaxLength(int[] nums) {
                int l = nums.length, one = 0, dif, ans = 0;
                int[] vis = new int[2 * l + 1];
                vis[l] = 1;
                for (int i = 0; i < l; i++) {
                    one += nums[i];
                    dif = 2 * one - i - 1;
                    if (vis[dif + l] > 0) {
                        ans = Math.max(ans, i + 2 - vis[dif + l]);
                    } else {
                        vis[dif + l] = i + 2;
                    }
                }
                return ans;
            }
        };
        int[] nums = {0,1,1,0,1,1,1,0};
        int maxLength = solution.findMaxLength(nums);

        System.out.println(maxLength);

    }

    static class Solution {
        public int findMaxLength(int[] nums) {
            Map<Integer,Integer> tmp = new HashMap<>(nums.length*2);
            int sum = 0;
            int res = 0;
            for (int i = nums.length - 1; i >= 0; i--) {
                System.out.print(nums[i]);
                sum+=nums[i];
                System.out.println("几个零："+(nums.length - i - sum));
                int i1 = nums.length - i - sum;
                if(sum -i1 == 0){
                    res = Math.max(res,nums.length - i);
                }
                Integer integer = tmp.get(sum - i1);
                if(integer != null){
                    res = Math.max(res,integer-i);
                }
                if(!tmp.containsKey(sum-i1)){
                    tmp.put(sum-i1,i);
                }

            }
            System.out.println(tmp);
            return res;
        }
    }
}
